package warm100;

import java.util.ArrayDeque;
import java.util.Deque;

public class maxSlidingWindow_239 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //维护一个单调递减的双端队列，队首（右边）为最大值，每遇到一个数都去掉前面比它小的数
        int n =nums.length;
        int[] ans = new int[n-k+1];//注意大小的计算，前k个只计算了一次
        Deque<Integer> q = new ArrayDeque<>();//双端队列存储有序元素的下标
        for(int i = 0; i < n; i++){
            //1.add
            //维护q的单调性
            //先判断非空，保证getLast（）有效；
            //在（左边）入队前，先判断上一个的大小，若小，则删掉再入队；否则直接入队
            while(!q.isEmpty() && nums[q.getLast()] <= nums[i]){
                q.removeLast();  //左边如果有小于当前遍历值的去掉
            }
            q.addLast(i);           //队尾入队，保证从左到右单调增加
            //2.remove
            //入队后，滑动窗口大小是否超过k，即最大值是否还有效
            //此时因为左边元素一定比右边元素来得晚，所以最右边的最大值已经离开了窗口，弹出队首（最右边）的数字
            //因为是逐个的，所以==也可以
            if(i - q.getFirst() >= k){
                q.removeFirst();
            }
            //3.record answer
            if( i >= k-1){//一个一个入队，直到至少有k个后才开始记录答案
                ans[i -k+1] = nums[q.getFirst()];//有序的所以返回第一个就行
            }
        }
        return ans;

    }
}
